// hdu 2089.不要62/数位dp
// 不吉利的数字为所有含有4或62的号码。
// 例如：62315 73418 88914 都属于不吉利号码。
// 但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
// 求[50, 2000]之间符合的数字有多少

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;

int l,r;
int f[11][11];
//f[i][j]表示i位数且最高位为j的方案数。
//对于f[i][j]这个状态，根据题意,
//f[i-1][k]必须满足k!=4,j!=4.且jk!=62.
void init() {
  for(int i=0;i<10;i++) f[1][i]=1;
  f[1][4]=0; // 个位数，排除4
  for(int i=2; i<11; i++){
    for(int j=0; j<10; j++){
      if(j==4) continue;
      for(int k=0;k<10;k++){
        if((j==6&&k==2)||k==4)
            continue;
        f[i][j] += f[i-1][k];
      }
    }
  }
}

int dp(int n){
  if(!n) return 1;
  vector<int> a; // 存储分割位数。
  int ans=0; //,last=0; // last保存上一位的值
  while(n) a.push_back(n%10),n/=10;
  a.push_back(0);
  for(int i = a.size()-2; i>=0; i--){
    int x = a[i];
    for(int j=0; j<x; j++){
      //走左边分支，我们需要判断
      if(j==4||(j==2&&a[i+1]==6))
          continue;
      ans += f[i+1][j];
    }
    if(x==4||(a[i+1]==6&&x==2))
        break;
    //last = x;
    if(!i)ans++;
  }
  return ans;
}

int getCount(int l, int r) {
    return dp(r) - dp(l-1);
}
